package com.nanbei.tree;

import java.util.LinkedList;

/**
 * @ClassDescription: 使用递归的方式遍历二叉树
 * @JdkVersion: 17
 * @Author: BaoShan.li
 * @Created: 2023/12/6 11:06
 */
public class BianLiTree {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(
                new TreeNode(new TreeNode(4), 2, null),
                1,
                new TreeNode(new TreeNode(5), 3, new TreeNode(6)));

        qianTree(treeNode);

        System.out.println();
        System.out.println("---------------------------------------------------");

        zhongTree(treeNode);

        System.out.println();
        System.out.println("---------------------------------------------------");

        houTree(treeNode);

        System.out.println();

    }

    /**
     *  使用递归方法前序遍历节点
     * @param treeNode 二叉树
     */
    public static void qianTree(TreeNode treeNode){

        if (treeNode == null){
            return;
        }

        System.out.print(treeNode.value + "\t");
        qianTree(treeNode.left);
        qianTree(treeNode.right);
        
    }

    /**
     *  使用递归方法  中序遍历节点
     * @param treeNode 二叉树
     */
    public static void zhongTree(TreeNode treeNode){

        if (treeNode == null){
            return;
        }


        zhongTree(treeNode.left);
        System.out.print(treeNode.value + "\t");
        zhongTree(treeNode.right);

    }

    /**
     *  使用递归方法 后序遍历节点
     * @param treeNode 二叉树
     */
    public static void houTree(TreeNode treeNode){

        if (treeNode == null){
            return;
        }

        houTree(treeNode.left);
        houTree(treeNode.right);
        System.out.print(treeNode.value + "\t");

    }

    /**
     * 非递归方法 进行 前序遍历和中序遍历
     * @param treeNode 二叉树
     */
    public static void qianAndZhong(TreeNode treeNode){

        // 设置栈记录从根节点开始向下遍历时去的路径
        LinkedList<TreeNode> route = new LinkedList<>();

        while (treeNode != null || !route.isEmpty()){
            // 当节点不为空时证明该节点存在左孩子
            if (treeNode!=null ){
                // 在此输出为前序遍历
                System.out.println(treeNode.value);
                // 将节点压入栈
                route.push(treeNode);
                treeNode = treeNode.left;
            }else {
                //当节点为空时证明该节点已经为叶子节点
                TreeNode pop = route.pop();
                // 在此输出为中序遍历
                System.out.println(pop.value);
                treeNode = pop.right;
            }

        }

    }



    /**
     * 非递归方法 进行后序遍历
     * @param treeNode 二叉树
     */
    public static void houBianli(TreeNode treeNode){

        LinkedList<TreeNode> nodeLinkedList = new LinkedList<>();

        // 定义一个临时变量用来记录 上一个输出节点
        TreeNode temp = null;
        while (treeNode != null || !nodeLinkedList.isEmpty()){
            if (treeNode != null){
                nodeLinkedList.push(treeNode);
                treeNode = treeNode.left;
            }else {
                // 先查看栈顶元素
                TreeNode peek = nodeLinkedList.peek();
                // 如果栈顶元素的右节点为空 或者 上一个输出的节点为栈顶元素的右节点
                // 则证明栈顶元素的左右孩子节点都已经遍历完成 可以弹出
                if (peek.right == null || temp == peek.right){
                    temp = nodeLinkedList.pop();
                    System.out.println(temp.value);
                }else {
                    // 如果右孩子不为空  或者 栈顶元素右孩子还没有遍历则需要遍历右孩子
                    treeNode = peek.right;
                }
            }
        }
    }


    /**
     * 树的前中后序遍历
     * @param treeNode 树的根节点
     */
    public static void bianLiTree(TreeNode treeNode){

        TreeNode root = treeNode;
        TreeNode befNode = null;
        LinkedList<TreeNode> nodeStack = new LinkedList<>();

        while (root != null || !nodeStack.isEmpty()){
            if (root != null){
                // 在此输出为前序遍历
                System.out.println("前："+root.value);
                nodeStack.push(root);
                root = root.left;
            }else {
                TreeNode peek = nodeStack.peek();

                if (peek.right == null){
                    // 右子树为空可以不处理，对中序来说，要在右子树打印之前处理

                    // 在此输出为中序遍历
                    System.out.println("中："+peek.value);

                    befNode = nodeStack.pop();

                    // 在此输出为后序遍历
                    System.out.println("后："+peek.value);


                }else if (befNode == peek.right){
                    // 右子树处理完成，对中序来说无需打印

                    befNode = nodeStack.pop();
                    // 在此输出为后序遍历
                    System.out.println("后："+peek.value);

                } else {
                    //右子树尚未处理，对中序来说，要在右子树处理之前打印

                    // 在此输出为中序遍历
                    System.out.println("中："+peek.value);
                    root = peek.right;


                }
            }
        }
    }
}
